#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef double db;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); }
	return x*f;
}
const int MAXN=1e6+10,MOD=1e9;
int n,f[MAXN];
int main()
{
	n=read();
	f[0]=1;
	for(int i=0;(1<<i)<=n;++i)
		for(int j=1;j<=n;++j)
			if(j-(1<<i)>=0)f[j]=((LL)f[j]+f[j-(1<<i)])%MOD;
	printf("%d\n",f[n]);
	return 0;
}
